package leetcode_181_200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class findRepeatedDnaSequences_187 {
    public List<String> findRepeatedDnaSequences(String s) {
        /**
         * 目前认为意思可能是每种截取中出现重复的，彼此不重叠
         * 一次遍历，统计所有
         */
        //AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT
        List<String> ans = new ArrayList<String>();
        HashMap<String,Integer> map=new HashMap<>();
        for(int i=0;i<=s.length()-10;i++){
            String part=s.substring(i,10+i);
            map.put(part,map.getOrDefault(part,0)+1);
            if(map.get(part)==2)  //出现超过三次无需再次添加
                ans.add(part);
        }
        return ans;
    }

   // 一是每次生成子串都是新的字符串（Java中字符串不可变）
    // 二是计算hash每次都是10个字符全部遍历一遍。
    //高级解法
    //自定义二进制哈希（int值表示）
   // 把ACGT四个字符映射到2位的数字
    static int[] MASK_MAP = new int[26];
    static {                                       //数组实际只用到4个位置
        MASK_MAP['A' - 'A'] = 0;
        MASK_MAP['C' - 'A'] = 1;
        MASK_MAP['G' - 'A'] = 2;
        MASK_MAP['T' - 'A'] = 3;
    }
    public List<String> findRepeatedDnaSequences2(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        if (n <= 10) {
            return ans;
        }

        // 记录每个hash出现的次数
        //把 ACGT 四个字符映射到 2 位的数字上，分别用二进制的 00、01、10、11 表示
        // 即 0、1、2、3，这样长度为 10 的子串一共只需要 20 位,  hash值也为二进制 ，范围 从0-2^20
        int[] map = new int[1 << 20];
        int hash = 0;
        //初始化第一个字符串的hash值
        for (int i = 0; i < 10; i++) {
            // 每2位一个字符, 计算新 hash 值
            hash = hash << 2 | MASK_MAP[s.charAt(i) - 'A'];  // hash << 2 将当前哈希值左移 2 位，腾出低 2 位空间以容纳新字符的掩码值。
                                                                                               //  |  操作将新字符的掩码值 MASK_MAP[s.charAt(i) - 'A'] 合并到哈希值的低 2 位中。
        }
        map[hash]++;

        //从第二个字符串开始，增删窗口左右的字符，并计算hash值
        //hash左边加入新字符，右边去除老字符
        for (int i = 1; i <= n - 10; i++) {
            // & 0xfffff （  保留低位20位）去除最高 2位
            hash = (hash << 2 | MASK_MAP[s.charAt(i + 10 - 1) - 'A']) & 0xfffff;  //左移两位即增添一位字符
            map[hash]++;
            // 因为不存在hash冲突，所以可以直接使用
            if (map[hash] == 2) {
                ans.add(s.substring(i, i + 10));
            }
        }

        return ans;
    }

}
